# 给你一个有 n 个节点的 有向无环图（DAG），请你找出所有从节点 0 到节点 n-1 的路径并输出（不要求按特定顺序）
#  graph[i] 是一个从节点 i 可以访问的所有节点的列表（即从节点 i 到节点 graph[i][j]存在一条有向边）。
#
#  示例 1：
# 输入：graph = [[1,2],[3],[3],[]]
# 输出：[[0,1,3],[0,2,3]]
# 解释：有两条路径 0 -> 1 -> 3 和 0 -> 2 -> 3
#
#  示例 2：
# 输入：graph = [[4,3,1],[3,2,4],[3],[4],[]]
# 输出：[[0,4],[0,3,4],[0,1,3,4],[0,1,2,3,4],[0,1,4]]
from typing import List


class Solution:
    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:
        """
        回溯法
        :param graph:
        :return:
        """
        res = []
        target = len(graph) - 1

        def backTrack(node: int, singleRes: List[int], visited: set) -> None:
            singleRes.append(node)
            visited.add(node)
            if node == target:
                res.append(list(singleRes))
            for neighbor in graph[node]:
                if neighbor not in visited:
                    backTrack(neighbor, singleRes, visited)
            visited.discard(node)
            singleRes.pop()
        backTrack(0, [], set())
        return res


if __name__ == "__main__":
    graph = [[4, 3, 1], [3, 2, 4], [3], [4], []]
    print(Solution().allPathsSourceTarget(graph))
